package club.xiaojiawei.dp;

import java.util.*;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 6/4/22 9:04 PM
 * @question 279. 完全平方数
 * @description 给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
 * 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
 */
public class NumSquares279 {

    public static void main(String[] args) {
        NumSquares279 test = new NumSquares279();
        int result = test.numSquares(12);
        System.out.println("最少数量："+result);
    }

    /**
     * dp-预处理
     * 时间复杂度 O(n倍根号n)
     * 时间复杂度 O(n)
     * @param n
     * @return
     */
    public int numSquares(int n) {
        ArrayList<Integer> goods = new ArrayList<>();
        int[] dp = new int[n + 1];
        for (int i = 1; i < n; i++) {
            if (i * i <= n){
                goods.add(i * i);
            }
            dp[i] = n;
        }
        dp[n] = n;
        for (Integer good : goods) {
            for (int i = good; i <= n; i++){
                dp[i] = Math.min(dp[i], dp[i - good] + 1);
            }
        }
        return dp[n];
    }

    /**
     * 官方-dp
     * 时间复杂度 O(n倍根号n)
     * 时间复杂度 O(n)
     * @param n
     * @return
     */
    public int numSquares2(int n) {
        int[] f = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int minn = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; j++) {
                minn = Math.min(minn, f[i - j * j]);
            }
            f[i] = minn + 1;
        }
        return f[n];
    }

    /**
     * 官方-数论-四平方和定理
     * 时间复杂度 O(根号n)
     * 时间复杂度 O(1)
     * @param n
     * @return
     */
    public int numSquares3(int n) {
        if (isPerfectSquare(n)) {
            return 1;
        }
        if (checkAnswer4(n)) {
            return 4;
        }
        for (int i = 1; i * i <= n; i++) {
            int j = n - i * i;
            if (isPerfectSquare(j)) {
                return 2;
            }
        }
        return 3;
    }

    // 判断是否为完全平方数
    public boolean isPerfectSquare(int x) {
        int y = (int) Math.sqrt(x);
        return y * y == x;
    }

    // 判断是否能表示为 4^k*(8m+7)
    public boolean checkAnswer4(int x) {
        while (x % 4 == 0) {
            x >>= 2;
        }
        return x % 8 == 7;
    }

    /**
     * 民间-BFS
     * <img src="https://zergqueen.gitee.io/images/279bfs.png">
     * @param n
     * @return
     */
    public int numSquares4(int n) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visit = new boolean[n + 1];
        queue.add(n);
        visit[n] = true;
        int level = 0;
        while (!queue.isEmpty()) {
            level++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Integer temp = queue.poll();
                for (int j = 1; j * j <= temp; j++) {
                    int rest = temp - j * j;
                    if (rest == 0) {
                        return level;
                    }
                    if (!visit[rest]) {
                        queue.add(rest);
                        visit[rest] = true;
                    }
                }
            }
        }
        return -1;
    }

    /**
     * 民间-贪心
     * @param n
     * @return
     */
    public int numSquares5(int n) {
        for (int i = 1; i * i <= n; ++i) {
            this.squareNums.add(i * i);
        }
        int count = 1;
//        贪心，从最小次数开始
        for (; count <= n; ++count) {
            if (isDividedBy(n, count))
                return count;
        }
        return count;
    }

    Set<Integer> squareNums = new HashSet<Integer>();

    protected boolean isDividedBy(int n, int count) {
        if (count == 1) {
            return squareNums.contains(n);
        }
        for (Integer square : squareNums) {
            if (isDividedBy(n - square, count - 1)) {
                return true;
            }
        }
        return false;
    }

}
